﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ExcelFileQueryTool
{
    public static class LevenshteinDistance
    {
        private static Dictionary<int, int> DistanceCache = new Dictionary<int, int>();

        /// <summary>
        /// 取最小的一位数
        /// </summary>
        /// <param name=”first”></param>
        /// <param name=”second”></param>
        /// <param name=”third”></param>
        /// <returns></returns>
        private static int Min(int first, int second, int third)
        {
            int min = Math.Min(first, second);
            return Math.Min(min, third);
        }
        /// <summary>
        /// 计算编辑距离
        /// </summary>
        /// <param name="str1"></param>
        /// <param name="str2"></param>
        /// <returns></returns>
        public static int GetDistance(string str1, string str2)
        {
            if (str1 == null && str2 == null)
                return 0;

            if (str1 == null || str1.Length == 0)
                return str2.Length;

            if (str2 == null || str2.Length == 0)
                return str1.Length;

            int distance;
            int cacheKey = str1.GetHashCode() ^ str2.GetHashCode();

            if (DistanceCache.TryGetValue(cacheKey, out distance) == false)
            {
                int len_1 = str1.Length;
                int len_2 = str2.Length;
                int[,] matrix = new int[len_1 + 1, len_2 + 1];

                for (int i = 0; i <= len_1; i++)
                    matrix[i, 0] = i;

                for (int i = 0; i <= len_2; i++)
                    matrix[0, i] = i;

                int temp = 0;

                for (int i = 1; i <= len_1; i++)
                {
                    var ch1 = str1[i - 1];

                    for (int j = 1; j <= len_2; j++)
                    {
                        temp = ch1.Equals(str2[j - 1]) ? 0 : 1;

                        matrix[i, j] = Min(matrix[i - 1, j] + 1, matrix[i, j - 1] + 1, matrix[i - 1, j - 1] + temp);

                    }
                }

                distance = matrix[len_1, len_2];
                DistanceCache.Add(cacheKey, distance);
            }

            return distance;
        }

        /// <summary>
        /// 计算字符串相似度
        /// </summary>
        /// <param name=”str1″></param>
        /// <param name=”str2″></param>
        /// <returns></returns>
        public static decimal GetSimilarity(string str1, string str2)
        {
            int val = GetDistance(str1, str2);

            if (val == 0)
                return 1m;
            else
                return 1m - (decimal)val / (decimal)Math.Max(str1.Length, str2.Length);
        }
    }
}
